#include <lversion.h>
#if L_VERSION_MODULE_DISJOINT_SET == 120130

#include "_ldisjointSet_120130.h"

#include <map>
using namespace std;

using namespace llib;
using namespace llib::util;

/* path compression */
Int32 DisjointSet::Find( Int32 elemId )
{
    BOOST_ASSERT(elemId >= 0 && elemId < _sz);

    Int32 groupId = elemId;
    // get root id
    while(groupId != _set[groupId])
        groupId = _set[groupId];
    // compress to root
    Int32 uperId;
    while(elemId != groupId) {
        uperId = _set[elemId];
        _set[elemId] = groupId;
        elemId = uperId;
    }
    return groupId;
}

void DisjointSet::Merge( Int32 elemId0, Int32 elemId1 )
{
    BOOST_ASSERT(elemId0 >= 0 && elemId0 < _sz);
    BOOST_ASSERT(elemId1 >= 0 && elemId1 < _sz);

    Int32 groupId0 = Find(elemId0);
    Int32 groupId1 = Find(elemId1);
    if(groupId0 > groupId1)
        _set[groupId0] = groupId1;
    else if(groupId0 < groupId1)
        _set[groupId1] = groupId0;
}

void DisjointSet::Arrange()
{
    // just call "find" operation from back to front
    // this will make arrange effectivly
    for(Int32 I = _sz - 1; I > -1; --I)
        Find(I);
}

IrregularTable<Int32>* DisjointSet::GetGroups()
{
    Arrange(); // arrange first

    struct GInfo { Int32 order; Int32 number; };
    map<Int32,GInfo> map;
    Int32 curGroupId = -1;
    Int32 groupOrder = -1;
    Int32* _set2 = new Int32[_sz];
    GInfo gInfo;
    // perpare map
    FOR(I,0,_sz) {
        if(curGroupId < _set[I]) {
            curGroupId = _set[I];
            ++groupOrder;
            gInfo.order = groupOrder;
            gInfo.number = 1;
            map[curGroupId] = gInfo;
            _set2[I] = groupOrder;
        } else {
            map[_set[I]].number += 1;
            _set2[I] = map[_set[I]].order;
        }
    }
    // perpare row size
    Int32 groupNum = groupOrder + 1, index = 0;
    vector<Int32> row_size(groupNum), row_number(groupNum,0);
    for(std::map<Int32,GInfo>::iterator i = map.begin(); i != map.end(); ++i) {
        row_size[index++] = i->second.number;
    }
    // perpare return value
    IrregularTable<Int32>* res = new IrregularTable<Int32>(row_size);
    IrregularTable<Int32>& res2 = *res;
    FOR(I,0,_sz) {
        res2[ _set2[I] ][ row_number[ _set2[I] ]++ ] = I;
    }
    delete[] _set2;

    return res;
}


#endif
